package com.leetcode;

public class Leetcode070 {

    /*
    //solution 1: f(n) = f(n-1) + f(n-2);
    //按照递推的思想，每次可以爬1个 或者 2个台阶，
    //f(n)代表可以爬到顶的方法,f(n-1)代表爬到倒数1个台阶的方法，f(n-1)代表爬到倒数2个台阶的方法
    //由于每次只能爬1个或2个台阶，那么必然有f(n) = f(n-1) + f(n-2);
    public int climbStairs(int n) {
        if(n<= 2){
            return n;
        }

        return (climbStairs(n-1)+ climbStairs(n-2));
    }
    */

    //solution 2: f(n) = f(n-1) + f(n-2);
    //在
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }


        //先手动算出 f0,f1,f2的结果
        int f0 = 0;
        int f1 = 1;
        int f2 = 2;
        for (int i = 3; i <= n; i++) {
            //相当于 f3 = f2 + f1；只不过用f2来存放最后的结果，f1则用来存放上次f2的值,f0用来存放f1
            f0 = f1;
            f1 = f2;
            f2 = f0 + f1;
        }

        return f2;
    }

    public static void main(String[] args) {
        Leetcode070 leetcode070 = new Leetcode070();
        System.out.println(leetcode070.climbStairs(3));
    }
}
